#include <iostream>
#include <string>

using namespace std;

// 前缀树
struct Node
{
    bool isEnd;
    struct Node *next[26];
};
class Trie
{
private:
    Node *root;

public:
    Trie()
    {
        root = new Node();
    }

    void insert(string word)
    {
        Node *cur = root;
        int n = word.size();
        for (int i = 0; i < n; i++)
        {
            int index = word[i] - 'a';
            // 插入节点先看看当前node是否已经有指向该字母的next指针
            // 如果没有则新建一个节点
            if (root->next[index] == nullptr)
            {
                root->next[index] = new Node();
            }
            cur = cur->next[index];

            if (i == n - 1)
            {
                cur->isEnd = true;
            }
        }
    }

    bool search(string word)
    {
        Node *cur = root;
        int n = word.size();
        for (int i = 0; i < n; i++)
        {
            int index = word[i] - 'a';
            if (root->next[index] == nullptr)
                return false;
            else
            {
                cur = cur->next[index];
                if (i == n - 1 && cur->isEnd == true)
                    return true;
                else if (i == n - 1)
                    return false;
            }
        }
        return false;
    }

    bool startsWith(string prefix)
    {
        int n = prefix.size();
        Node *cur = root;
        for (int i = 0; i < n; i++)
        {
            int index = prefix[i] - 'a';
            if (cur->next[index] == nullptr)
                return false;
            if (i == n - 1)
                return true;
            cur = cur->next[index];
        }
        return false;
    }
};
